/**
 * 
 */
package search;

import junit.framework.Assert;
import lib.util.Mutable;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a> Question:
 *         http://www.sureinterview.com/shwqst/542002
 */
public class BinarySearchOnRotatedArray {

	/*
	 * Find the key in the rotated array with the start and end position info
	 */
	int find(Integer[] rotArr, Integer key, Integer lo, Integer hi) {
		// if the array has a break point, mapping the hi index to the right.
		// for example, if the rotated array is {3,4,1,2}, imagine the array is
		// extended as {3,4,1,2, 3,4,1,2}
		int length = rotArr.length;
		if (hi < lo) {
			hi += length;
		}

		// binary search.
		while (hi >= lo) { // the minimum sub array is empty.
			int mid = (lo + hi) / 2;
			Integer midVal = rotArr[mid % length];

			// found the key
			if (midVal == key)
				return mid % length;

			if (midVal > key) {
				// lower the high boundary.
				hi = mid - 1;
			} else {
				// raise the low boundary.
				lo = mid + 1;
			}
		}
		// when return, the subarray rotArr[ lo...hi ] is empty.
		return -1;
	}

	/**
	 * Find the key in the rotated array without the start / end position info
	 * 
	 * @param rotArr
	 * @param key
	 * @return
	 */
	int find2(Integer[] rotArr, Integer key) {
		int lo = 0;
		int hi = rotArr.length - 1;

		// binary search
		while (lo <= hi) {
			int mid = (lo + hi) / 2;

			// found the key
			if (rotArr[mid] == key)
				return mid;

			// determine where the key should fall into, the left side or the
			// right side. check http://yes.sureinterview.me/shwqst/542002
			if (rotArr[lo] < rotArr[mid]) {
				if (rotArr[lo] <= key && key < rotArr[mid]) {
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			} else if (rotArr[lo] > rotArr[mid]) {
				if (rotArr[mid] < key && key <= rotArr[hi]) {
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			} else {
				/*
				 * special handing rotArr[lo] == rotArr[mid] == rotArr[hi].
				 * check lo and advance one element.
				 */
				if (rotArr[lo] == key)
					return lo;
				lo++;
			}
		}
		return -1;
	}

	/**
	 * Find the start and end position of the sorted array.
	 * 
	 * @param rotArr
	 *            the rotated sorted array
	 * @param start
	 *            the start position of the sorted array
	 * @param end
	 *            end position
	 */
	void findStartEndPosition(Integer[] rotArr, Mutable<Integer> start,
			Mutable<Integer> end) {
		int lo = 0;
		int hi = rotArr.length - 1;

		// the array is sorted correctly. no break points.
		if (rotArr[lo] < rotArr[hi]) {
			start.setValue(lo);
			end.setValue(hi);
			return;
		}

		// binary search for the break point
		/*
		 * the size of the minimum subarray is 2. So, when this loop terminates,
		 * rotArr[lo] > rotArr[hi] and lo + 1 = high;
		 */
		while (lo + 1 < hi) {
			int mid = (lo + hi) / 2;
			if (rotArr[lo] > rotArr[mid]) {
				// The lower part has the break point.
				hi = mid;
			} else if (rotArr[lo] < rotArr[mid]) {
				// The higher part has the break point.
				lo = mid;
			} else {
				/*
				 * when rotArr[lo] == rotArr[mid] == rotArr[hi], we can not tell
				 * which part has the break point, check one element at a time
				 * instead.
				 */
				if (rotArr[lo] > rotArr[lo + 1]) {
					start.setValue(lo + 1); // check if lo is the break point.
					end.setValue(lo);
					return;
				}
				lo++;
			}
		}
		start.setValue(hi);
		end.setValue(lo);
	}

	@Test
	public void test() {
		Integer[][] rotArr = new Integer[][] { //
		//
				{ 0, 1, 2, 3, 4, 5 },//
				{ 0, 1, 2, 3, 4, 4, 5 },//
				{ 0, 1, 2, 4, 4, 5 },//
				{ 0, 1, 2, 2, 4, 4, 5 },//
				{ 0, 1, 2, 2, 2, 4, 4, 5 },//
				{ 0, 1, 2, 3, 4, 4, 5 },//
				{ 0, 1, 1, 1, 1 },//
				{ 0, 1, 1, 1, 1, 1 },//
				{ 0, 1 },//
				{ 0 },//
				{ 1 },//
				{ 0, 1, 2, 3 },//
				{ 1, 2, 3, 4 },//
				{ 1, 2, 3, 4, 5 },//
		};

		for (Integer[] element : rotArr) {
			// check each array and rotate them.
			Integer[] va = element;
			Mutable<Integer> start = new Mutable<Integer>(), end = new Mutable<Integer>();

			for (int j = 0; j < va.length; j++) {
				// check results
				findStartEndPosition(va, start, end);
				Assert.assertEquals(//
						find(va, 0, start.getValue(), end.getValue()), //
						find2(va, 0));

				// rotate the array
				Integer tmp = va[0];
				for (int k = 0; k < va.length - 1; k++) {
					va[k] = va[k + 1];
				}
				va[va.length - 1] = tmp;
			}
		}
	}
}
